In image processing, it is often useful to generate a Fourier transform of an image. For example, in order to filter noise from an image, one may generate a forward Fourier transform of the image, filter the Fourier transform, and generate a reverse Fourier transform to produce an image without the noise. The advantage of performing the Fourier transform is that in the frequency domain of the Fourier transform, it may be easier to identify noise and filter it. Once the noise has been removed, the reverse Fourier transform will generate the image without the noise.
Generating a Fourier transform of an image using any type of direct implementation of the Fourier transform mathematics is a very time consuming operation even on fairly sophisticated computers. Using a fast Fourier transform (FFT) algorithm will greatly reduce the number of arithmetic operations required to generate a forward or reverse transform on a computer, but a low end general purpose computer may still require in excess of thirty minutes to an hour to perform the computation for a two dimensional image array of 512 pixels.times.512 pixels that is typically used in image processing. A high performance computer like a Vax/780 with substantial memory can perform the fast Fourier transform algorithm in approximately five seconds, but the cost of such computer may prove prohibitive for many applications. Thus, a need exists for an image processor utilizing a low end general purpose computer and special circuitry for generating forward and reverse Fourier transforms more rapidly. The present invention provides this specialized circuitry necessary to perform fast Fourier transform operations under the control of a general purpose computer.
In accordance with the present invention, an image processor for processing data representing an image includes specialized circuitry for operating on the data in a manner useful for performing a Fourier transform. The special circuitry of the image processor includes first and second memories, each for storing the data as an array of numbers in a format having rows and columns of data positions. Means are provided for scrolling the data in each row of the second memory with respect to the first memory by at least one data position. A data processor is provided and further means are provided for outputting the scrolled data of the second memory and the data of the first memory to the data processor. The data processor operates on the data to combine every other group of at least one number of each row of the scrolled data with a corresponding every other group of at least one number of each row of the data from the first memory and for passing to its output the data from the first memory for the remaining data positions to produce a new array of data that is useful in performing a fast Fourier transform.
In accordance with a more particular embodiment of the present invention, an image processor for performing a Fourier transform operation on data representing an image includes first and second memories and, each memory stores the data as an array of numbers having x rows and y columns. Control means in the form of a computer are provided for scrolling the data in each row of the second memory in a selected direction, forwardly or rearwardly, with respect to the first memory by a selected scroll number, n, of data positions (memory locations). The control means also generates control signals and selects the direction of scrolling and the number n of data positions by which the data is scrolled. A data processor is provided, and means are provided for outputting the data of the first memory and the scrolled data of the second memory to the data processor. The data processor operates in response to the control signals to define a data group as n numbers, to combine odd groups of n numbers in each row of data from the first memory with corresponding odd groups of n numbers in each row of the scrolled data from the second memory and to pass even groups of n numbers in each row of data from the first memory when the data in the second memory is scrolled forwardly by n data positions. The data processor is also operable to combine even groups of n numbers in each row of the data from the first memory with corresponding even groups of n numbers of scrolled data from the second memory and to pass odd groups of n numbers in each row of data from the first memory when the data is scrolled rearwardly by n data positions. The control means, preferably in the form of a small general purpose computer, is operable to cause the circulation of the data from the first and second memories to the data processor and back to the first and second memories for a series of circulation sets, where a circulation set is defined as a sufficient number of passes of the data through the data processor to combine the odd groups and pass the even groups to produce an intermediate array, store the intermediate array in the first memory and, then, to combine the even groups and pass the odd groups to produce a result array and store the result array in the first and second memories.
In the apparatus described above, the control means selects a scroll number n for each circulation set that is equal to the number "2" raised to a power of one less than the circulation set number, and the control means is further operable to circulate the data for a series of c circulation sets where two raised to the c power equals y, the number of columns of data. The more particular embodiment of the invention as described above is useful in performing a one dimensional FFT on an array of data, and by performing two one dimensional fast Fourier transforms on an array of data, a two dimensional transform may be generated.
In accordance with a particular method of the present invention, an array of data having x rows and y columns representing an image is processed as a part of a Fourier transform process using first and second memories and a data processor. The data is first reordered in accordance with a predetermined reordering sequence to produce reordered data, and the reordered data is stored in the first and second memories as an array of numbers. The data is circulated from the memories to the data processor and back to the memories for a first series of circulation sets, where the number of circulation sets in the first series equals c1 and two raised to the c1 power equals y, to produce a one dimensional fast Fourier transform array. Next, the one dimensional fast Fourier transform array is transposed by rows and columns so that the rows become columns and the columns become rows, and the data is again reordered and circulated from the memories to the data processor and back to the memories for a second series of circulation sets where the number of circulation sets in the second series equals c2 and two raised to the c2 power equals x, whereby the fast Fourier transform of the image is produced.
Each circulation set of the first and second series described above includes the steps of scrolling the data in each row of the second memory with respect to the first memory by s data positions where s equals two raised to the power of the number of the circulation set in a series of circulation sets, so that s equals one on a first circulation set, s equals two on a second circulation set, s equals four on a third circulation set and s equals two raised to the power of one less than the number of a last circulation set. The data of the first memory and the scrolled data of the second memory is then output to the data processor, and each row of the data of the first memory and the scrolled data of the second memory is grouped into alternating groups with s numbers in each group. In the data processor, every other group (defined as odd groups) of each row of the data from the first memory is combined with a corresponding group of each row of the scrolled data, and the data from the first memory is passed to the output of the data processor for the remaining data positions (the even groups) to produce an intermediate array of data. The intermediate array of data is stored in the first memory and the data in each row of the second memory is oppositely scrolled with respect to the first memory by s data positions and in an opposite direction from the previous scrolling to produce oppositely scrolled data. The intermediate array of data from the first memory and the oppositely scrolled data from the second memory is transmitted to the data processor and the data processor again groups each row of the data from the first and second memories into alternating groups with s numbers in each group. On this pass, the data processor combines the remaining every other group (the even groups) of each row of the intermediate data array, which is the data that was passed in the other combining and passing step, with a corresponding group of each row of the oppositely scrolled data and the data processor passes the data of the odd groups to its output and thereby produces a resulting array of data which is stored in the first and second memories.
In the combining steps of the above described method, the data from one of the memories is multiplied by a predetermined coefficient to produce a product and this product is added or subtracted to the data from the other memory. In a particular form of the present invention, the data processor is operable to combine the odd groups by multiplying the scrolled data by predetermined coefficients to produce products and adding the products to the data from the first memory, and the data processor is operable to combine the even groups by multiplying the data from the first memory by predetermined coefficients to produce a product and subtracting the product from the oppositely scrolled data.
In the discussion of the apparatus and method above, various operations have been performed on rows of data. For example, the data was scrolled by row and grouped by row. It will be understood, however, that the distinction between a row and a column is merely one of orientation and that all of the operations performed by row could be performed by column as well. Also, in the preferred embodiment, operations are performed on columns by first transposing the rows and columns so that the columns become rows. This transposition results in an effective and efficient method for performing operations on columns, but it will be understood that the same operations could be performed on the columns directly, without transposition.